# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
#
# @param root TreeNode类
# @return int整型
#
'''
思路就是返回的值是左中右，而不是原来的只有做或者只有右
max的值会实时的更新，也就是在线处理
'''
class Solution:
    def maxPathSum(self, root):
        # write code here
        self.res = float('-inf')  # 负无穷

        def dfs(root):
            if not root:
                return 0
            l = dfs(root.left)
            r = dfs(root.right)
            self.res = max(self.res, root.val + l + r)
            return max(0, max(l, r) + root.val)

        _ = dfs(root)
        return self.res